class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num + 1, 0);

        for(int i = 1, j = 1; i <= num; i += j, j *= 2) {
            for(int k = i; k < i + j; k ++) {
                if (k <= num) {
                    ret[k] = ret[k - j] + 1;
                }
            }
        }

        return ret;
    }
};